package LinkedList;

import Mylinkedlist.TestDemo;

/**
 * Created with IntelliJ IDEA.
 *
 * Description:
 * User: adol book
 * Date: 2022-05-02
 * Time: 7:29
 */
public class Linkedlist {
    static public class LinkNode{
        public int val;
        public LinkNode next;

        public LinkNode(int val) {
            this.val = val;
        }
    }
       public LinkNode head;
       public void craeatived(){
           LinkNode linkNode1 = new LinkNode(12);
           LinkNode linkNode2 = new LinkNode(23);
           LinkNode linkNode3 = new LinkNode(34);
           LinkNode linkNode4 = new LinkNode(45);
           LinkNode linkNode5 = new LinkNode(56);
           linkNode1.next = linkNode2;
           linkNode2.next = linkNode3;
           linkNode3.next = linkNode4;
           linkNode4.next = linkNode5;
           this.head = linkNode1;


       }

       public void addFirst(int data){
        //头插法
            LinkNode node = new LinkNode(data);
            node.next =this.head;
            this.head = node;
    }

        public void addLast(int data){
        //尾插法
            LinkNode node = new LinkNode(data);
            if(this.head == null){
              this.head = node;
            }else {
                LinkNode cur = this.head;
                while (cur.next != null){
                    cur = cur.next;
                }
                cur.next = node;
            }
        }
        private void isinligaddIndex(int index){
           if(index < 0 || index > size()){
               throw new isinligaddIndexExcation("插入元素时，index位置不合法");
           }

        }
        private LinkNode findaddIndex(int index){
           LinkNode cur = this.head;
           if(index-1 != 0){
               cur = cur.next;
               index--;
           }
           return cur;
        }
        public void addIndex(int index,int data)throws isinligaddIndexExcation {
        //任意位置插入
            isinligaddIndex(index);
            if(index == 0){
                addFirst(data);
                return;
            }
            if(index == size()){
                addLast(data);
                return;
            }
            LinkNode node = new LinkNode(data);
            LinkNode cur = findaddIndex(index);
            node.next = cur.next;
            cur.next = node;
        }
        public boolean contains(int key) {
            //查找是否包含关键字key是否在单链表当中
            LinkNode cur = this.head;
            while (cur != null) {
                if (cur.val == key) {
                    return true;
                }
                cur = cur.next;
            }
            return false;
        }
        public void remove(int key) {
        //删除指定位置
            if(this.head == null){
                throw new isinligaddIndexExcation("此链表为空，不能进行删除");
            }
            if(this.head.val == key){
                this.head = this.head.next;
            }
            LinkNode cur = this.head;
            while (cur != null){
                if(cur.next.val == key){
                    LinkNode del = cur.next;
                    cur.next = del.next;
                    return;
                }
                cur = cur.next;
            }
        }
         //删除所有值为key的节点
            public void removeAllKey(int key){
                if(this.head == null){
                    return;
                }
                LinkNode cur = this.head.next;
                LinkNode prev = this.head;
                while (cur != null){
                    if(cur.val == key){
                        prev.next = cur.next;
                        cur = cur.next;
                    }else {
                        prev = cur;
                        cur = cur.next;
                    }
                }
                if(this.head.val == key){
                    head = head.next;
                }
            }
        public int size() {
        //得到单链表的长度
            int count = 0;
            LinkNode cur = this.head;
            while (cur != null){
                count++;
                cur = cur.next;
            }
            return count;
        }
        public void display() {
        //遍历链表
            LinkNode cur = this.head;//不能改变头结点的位置
            while (cur != null){
                System.out.print(cur.val+" ");
                cur = cur.next;
            }
            System.out.println();
        }
        public void clear(){
        //清空
            LinkNode cur = this.head;
            LinkNode curNEXT = null;
            while (cur != null){
                curNEXT = cur.next;
                cur.next = null;
                cur = curNEXT;
            }
           this.head = null;
        }
}
